package demo;

public class BSTree {
   //非递归实现检测二叉搜索树中是否包含某元素
    private  boolean contains非递归(BSTNode root,int val){
        //用一个引用指向根结点
        BSTNode cur=root;
        //不为空进入循环
        while(cur!=null){
            //val相等表明找到了
            if(cur.val==val){
                return true;
            }else if(cur.val>val){
                //val小了 去左子树找
                cur=cur.left;
            }else{
                //val大了 去右子树找
                cur=cur.right;
            }
        }
        //循环结束 cur==null,没找到，返回false
        //若根结点为空 直接返回false
        return false;
    }

    //递归实现检测二叉搜索树中是否包含某元素
    private boolean contains递归(BSTNode root,int val) {
        //如果根结点为空
      if(root==null){
          //直接返回false
          return false;
      }
      //若根结点不为空
      if(root.val==val){
          //相等时返回true
          return true;
      }
      if(val<root.val){
          //val小了 去左子树查找
          return contains递归(root.left,val);
      }else{
          //val大了去右子树查找
          return contains递归(root.right,val);
      }
    }
    
}
